Chapter 17 Linear List Manipulation, Stacks and Queues
Note the following:-
17.2. Basics of data structures and lists in Python
17.2.3. List operation: traversal
Traversal of a list can be done in following ways:
a. Traversing a list using a for loop:
In a list there are indexes and items. In some situations you may need only the items, while in other you may need the items as well as the index of the items.
If you want only the items (and not the index) of a list, you may use the for loop as follows:
This script is available on page 410 of the book
L = ['a', 1, 'b', 2]
for x in L: # The variable x will hold each item of L one by one
print(x)
b. Traversing a list using a while loop:
You can use a while loop to traverse a list. But to do so you must first find the length of the list using the len() built-in function in Python. Then you may iterate over each item by using a counter. This is shown in the following example:
This script is available on page 411 of the book
L = ['a', 'b', 'c']
count = 0
while count < len(L):
print('at index-> ', count, 'is-> ',L[count])
count = count + 1
c. Traversing list using range and len:
Another way of traversing a list could be to first find out the number of elements in the list and then use a “for” loop. You can find the number of elements in a list by using the len(some_list) in-built Python function. A sample program is as follows:
This script is available on page 411 of the book
myList = ['a', 'b', 'c']
for index in range(len(myList)):
print('Index-> ',index,'Item->', myList[index])
17.2.4. Short note on Insertion
Two well-known methods to (1) insert an item in a list and (2) insert another list in a list are append() and extend().
Example of their use are as follows:
myList1 = ['a', 'b', 'c', 'd']
myList2 = ['1', '2', '3']
myList1.append('e') # append() is for adding an item
print(myList1) # prints ['a', 'b', 'c', 'd', 'e']
myList1.extend(myList2) # extend() is for adding another list
print(myList1) # prints ['a', 'b', 'c', 'd', 'e', '1', '2', '3']
But suppose you want to insert an item in a sorted list. But before you insert an item in a sorted list, you need to understand the functions and methods available in Python for sorting a list.
sorted() which takes a list object as a parameter and sorts the list give to the function as a parameter. sort() method which acts on a list object (using a dot operator).
Example of use of sorted() function and sort() method on a list is as follows:#... ON IDLE ...
>>> L = [4,3,1,2]
>>> sL = sorted(L) # sorted(L) takes L as a parameter
>>> L # Original list L is not modified
[4, 3, 1, 2]
>>> sL # Rather a new sorted list sL is created
[1, 2, 3, 4]
>>> L.sort() #Since L is a list, it has an inbuilt sort() method
>>> L # Using sort() changes the original list L.
[1, 2, 3, 4]
17.2.7. insort(sequence, item) method
The insort(sequence, item) method of bisect module inserts item into the sequence, keeping it sorted. Here, two methods of the bisect module are used .
bisect() method of the bisect module and it returns the index where the element is to be inserted in the list. insort() method of the bisect module which returns a sorted list. To sort the list you need only the insort() method. But if you need to know the index where the item was inserted in the list, then you need the bisect() method. The bisect() method does not modify the list. It simply tells at what index, the item will be inserted (if it is inserted).
This script is available on page 413 of the book
>>> import bisect
>>> L = [1,3,5,7,9]
>>> bisect.bisect(L, 6) # Returns index where item ie 6 to be inserted
3
>>> bisect.insort(L,6) # item 6 inserted so list remains in ascending order
>>> L
[1, 3, 5, 6, 7, 9]
>>>
The following script generates five random numbers in the range (0, 10) and add them one by one to an initial empty list in a sorted order:
This script is available on page 413 of the book
import random
import bisect
random.seed(1)
L = []
for count in range(6): # for loop executed 5 times
item = random.randint(0,100) # generates random int which can be 0 to 100
i = bisect.bisect(L, item) # gives index where item is to be inserted
bisect.insort(L, item) # inserts item in list maintaining ascending order
print(item, 'inserted at index-> ',i, ' List is->', L)
17.3.1. Inserting an item in a sorted list manually
This method applies when you have been given a sorted list of numbers (ascending/ descending) and you are asked to “insert” a number so that the sort does not get disturbed. The steps in the implementation are:
+’ operator. ExitempL2. Suppose the lower part of the broken list is tempL1, the number to be added is converted into tempL2 and the upper part of the list is tempL3. Then the final list will be tempL1 + tempL2 + tempL3The script below shows the implementation of algorithm where an item is inserted in a sorted list:
This script is available on page 414 of the book
def findIdx(myL, item): # Function gets index where item be inserted in myL
idx_val = 0
if item <= myL[0]:# Item to be inserted<smallest item in list
print('item is less than or equal to least item in list')
return (-1)
if item >= myL[len(myL)-1]:# Item to be inserted > biggest item in list
print('item is greater than or equal to least item in list')
return (len(myL) -1)
for idx_count in range(len(myL)):
if item <= myL[idx_count]:
idx_val = idx_count
return (idx_val-1)
def insertItemInList(inputList, inputItem):
idxVal = findIdx(inputList, inputItem)
if idxVal == -1:
itemAddedList = [inputItem] + inputList#Add number at beginning of list
print(itemAddedList)
elif idxVal == len(inputList) - 1:
itemAddedList = inputList + [inputItem]# Add number at end of list
print(itemAddedList)
else:
tempL1 = inputList[0: idxVal + 1]#tempL1 has numbers< number to be added
tempL2 = [inputItem]
tempL3 = inputList[idxVal+1:] # tempL3 has number >than one to be added
itemAddedList = tempL1 + tempL2 + tempL3
print(itemAddedList)
# Test lists
print('Using list[1,2,3,4,5],adding 0')
insertItemInList([1,2,3,4,5], 0)
print('Using list[1,2,3,4,5], adding 7')
insertItemInList([1,2,3,4,5], 7)
print('Using list[1,2,3,4,5], adding 2.5')
insertItemInList([1,2,3,4,5], 2.5)
17.3.2. Deleting an item whose “index” is given from a list (sorted or unsorted)
The algorithm is shown visually in Figure 17.2 in the book using a sample list [10,20,30,40,50,60,70,80] from which number at index 3, i.e., 40 is to be removed
The following script has a function which takes two parameters as inputs, the first is the list and the second is the index of the item to be deleted. The program is as follows:
This script is available on page 417 of the book
def fDelL(L, idx):
if idx > len(L)-1 or idx <0: # Check to ensure index is in range
print('Index not in range')
return -1
else:
xL = L[:] # Copy list into a local variable
for v in range(idx,len(xL)-1):
print(v)
xL[v] = xL[v+1]
print(xL, 'Item at index', v+1, 'copied to index', v)
# This print shows progress of deletion
xL = xL[0:len(L)-1] # need to discard the last element
return(xL)
myL = [10, 20, 30, 40, 50, 60, 70, 80]
idx = 3
delList = fDelL(myL, idx)
print(delList, 'After deleting item at', idx )
A second way of deleting an item:
You can delete an item by
+’ operator.This is shown in the script below:
This script is available on page 418 of the book
def fDelL(L, idx):
if idx > len(L)-1or idx <0:
print('Index not in range')
return -1
else:
lowL = L[0:idx] #This is lower part of list
print('Lower part of list ', lowL)
uppL = L[idx+1: len(L)] # This is upper part of list
print("Upper part of list", uppL)
newL = lowL + uppL # Concatenate or add the two lists
return(newL)
# ... TEST ...
myL = [10,20,30,40,50,60,70,80]
idx = 3
L2=fDelL(myL, idx) # Item at index 3 ie 4th deleted
print('List after deletion of item at index',idx, 'is ', L2)
17.3.3. Linear search
In a search you have an item being searched which you may call “pattern” and you have some “collection” of items. In a linear search you compare the “pattern” to each item in the container until you succeed or all items in the container are compared. In common Python scripts, this container is generally a list. Figure 17.4 (In the book) gives a “visual representation” of the process of linear search.
The script which implements this is as follows:
This script is available on page 419 of the book
def fLSearch(myL, myItem):
for i in range(len(myL)):
if myL[i] == myItem:
return i # if myItem found, terminate function. Return index
return -1# If not found, return -1 after looping over each element of list
L = [1,3,4,5,6,8]
idx = fLSearch(L, 8)
if idx == -1:
print('Item not found')
else:
print('Item found at index-> ',idx)
17.3.4. Binary search
The following script shows how binary search works
This script is available on page 420 of the book
def fBSearch(myL, itm):
L = 0
R = len(myL) - 1
print('Initially R is-> ', R)
while True:
if R < L:# This happens only if item not in list
return -1
M = (L+ R)//2
print('M -> ',M)
if myL[M] < itm:
L = M + 1
print('L-> ',L, 'List to be searched', myL[L:R])
elif myL[M] > itm:
R = M - 1
print('R-> ', R, 'List to be searched', myL[L:R])
else:# Executed only if myL[M] == itm
return M
# Test the function
L = [21, 32, 33, 44, 56, 57, 68, 79, 81, 92, 100, 101]
idx = fBSearch(L, 92)
if idx == -1:
print('Item not found ')
else:
print('Item found at index-> ', idx)
17.3.5. Binary search (using recursion)
You can search for an item in a list sorted in ascending order by using recursion also. The steps are as follows:
The following script does a binary search on a sorted list using recursion:
This script is available on page 423 of the book
# Script implements binary search using recursion.
# Returns the index of n if present in list L, else -1
import random
def fBRecur (L, left, right, n):
# If n smaller than smallest or bigger than biggest-> Not in the list
if n < L[left] or n > L[right]:
return -1
if right >= left:
mid = int(left + (right - left)/2)
# If item is at middle itself
if L[mid] == n:
return mid
# If item is smaller than mid, then
# could only be in left half of list
elif n < L[mid]:
right = mid - 1
return fBRecur(L, left, right, n)
# Else the element can only be present in right half of List
else:
left = mid + 1
return fBRecur(L, left, right, n)
else:
return -1
# Take a list with items sorted in ascending order
L = [ 3, 4, 5, 6, 7, 10, 11, 13, 15, 18, 20]
#Following generates 5 random integers [0, 25] and
#sees if they are present in the list
rL = []# This list will store the random numbers generated
for x in range(5):
n = random.randint(0, 25) # generate random integers in range [0, 25]
rL = rL +[n]
answer = fBRecur(L, 0, len(L)-1, n)
if answer == -1:
print(n, "Item not in the list")
else:
print(n, "Item in list at index", answer)
print('list of randoms->', rL)
17.3.6. Selection sorting
The steps in sorting a list using selection sort are:
The code is shown as follows:
This script is available on page 426 of the book
# Script implements selection sort
def selSort(myL):
lenL = len(myL)
print(myL, ' -> Original List')
for p in range(lenL - 1):
print(myL, 'Comparing item at index-> ', p)
for s in range(p + 1, lenL):
if myL[s] < myL[p]:
temp = myL[p]
myL[p] = myL[s]
myL[s] = temp
print('\t', 'Exchange idx ->', p, ' with idx ->', s, myL)
print(myL, ' -> Final sorted list')
return(myL)
# Test
testL = [7, 1, 4, 2, 0]
selSort(testL)
17.3.7. Bubble sort
len() function. You will have two for loops. The outer for loop is called a pass (denoted by variable p) and the inner for loop is called a step (denoted by variable s).lenL (note if you have a list of 5 items then lenL is 5, but index in the list are from 0 to 4, and the passes will be from 0 to 3, i.e., 1 less than the index of the last item in the list. This is because in each pass you are comparing the item at index, to all the items on its right. So you need to go up till only the second last item, since the last item does not have anything to its right). Here the variable p is used to denote the pass number. If there are 4 items in the list, i.e., lenL =4, then there will be total 3 passes, i.e., pass0 (with p =0), pass1 (with p=1), and pass2 (with p =2). So number of passes can be generated using the range(0,lenL-1). p = 0, the step variable s of the inner loop must go on comparing till the end of the list. Hence, if there are say 6 items in the list, i.e., lenL = 6, then when p = 0, s will vary from 1 to index of 6th item, i.e., 5, so the range function used for s will be range(1, lenL-p). Similarly in the next pass, i.e., when outer counter is p = 1, then it means that one item has already “bubbled” to the end of the list. So the inner variable needs to go up to only second last item in the list. This is why the range function of the inner loop has the form range(1, lenL-p).(s-1) is compared to the item at next index, i.e., s. If the item at index (s-1) is greater it is exchanged, else not.# bubble sort function
def fBsort(myL):
lenL = len(myL)
for p in range(0, lenL -1):
print('Step p =', p)
for s in range(1,(lenL-p)):
if myL[s-1] > myL[s]:
temp = myL[s - 1]
myL[s - 1] = myL[s]
myL[s] = temp
print('Item at index', s-1, 'compared to item at index',s,myL)
#
# test on [4,3,2,1,7,6,1]
L = [4,3,2,1,7,6,1]
fBsort(L)
print(L)
It is a simple modification to change the bubble sort to sort in descending order. The program is listed as follows:
This script is available on page 430 of the book
# bubble sort function
def fBsort(myL):
lenL = len(myL)
for p in range(0, lenL -1):
print('Step p =', p)
for s in range(1,(lenL-p)):
if myL[s-1] < myL[s]:
temp = myL[s - 1]
myL[s - 1] = myL[s]
myL[s] = temp
print('Item at index', s-1, 'compared to item at index',s,myL)
#
# test on [4,3,2,1,7,6,1]
L = [4,3,2,1,7,6,1]
fBsort(L)
print(L)
17.3.8. Insertion sort
The best way to think of insertion sort is as if you deal with cards one by one and you arrange them in ascending order.
Call the card dealt as “key”. So, now the cards are in three parts.
Suppose you have cards 1,4 and 6 in your hand and you start with card 3. Further suppose that cards 9, 2 and 5 will come later.
You could represent this as: [1, 4, 6] {3} [9, 2, 5].
• Here [1,4,6 ]and [9,2,5] are used to represent the sorted and unsorted lists and {3} is for the key.
So now when
[1,3,4,6]{9}[2,5]. [1,3,4,6,9]{2}[5].[1,2,3,4,6,9]{5}.[1,2,3,4,5,6,9]. This script is available on page 432 of the book
def fInsSort(myL):
print('original list-> ', myL)
for key in range(1,len(myL)):
j = key - 1
while j >= 0:
if myL[key] < myL[j]:
temp = myL[key]
myL[key] = myL[j]
myL[j] = temp
print('item', key, 'compared to', j, 'Exchange ', myL)
key = key-1
j = j - 1# This is a decrementing while loop
else:
print('item', key, 'compared to', j, 'No Exchange', myL)
break
# ... TEST THE FUNCTION...
L =[6,4,5,2,3]
fInsSort(L) # Call the function
print(L, '-> Final list')
17.4.3. Implement stack using a class
The following script implements a stack as a class named CStack. It has 4 methods:-
__init__(). This method simply creates an attribute myS and initializes it as an empty list.push(). This method pushes an item on to the stack.myPop(). This method pops an item from the stack, but before doing so it checks that the stack is not empty.stRev(). This method prints the items in the stack in reverse order (Item pushed last is printed first), but before printing the stack in reverse, it checks that the stack should not be empty.The rest of the code creates an instance of the stack class CStack and uses it. The script is shown below:-
This script is available on page 435 of the book
class CStack:
def __init__(self): # Creates myS an empty list
self.myS = []
print('Stack created')
def push(self, item): # Push items to stack
self.myS.append(item)
print(item, ' pushed to stack')
def myPop(self): # pop from list but check before that stack not empty
if len(self.myS) == 0: # Stack empty so dont pop
print('Nothing to pop')
else: # Stack not empty so pop
pI = self.myS.pop()
print(pI, '-> deleted from stack')
return pI
def stRev(self): # print stack reversed but check before that stack not empty
s = len(self.myS)
if s == 0: # stack empty. Dont print
print('Stack empty')
else: # Stack not empty so print
for idx in range(s - 1, -1, -1):
print('At index', idx, 'Value', self.myS[idx])
# Script to create a CStack object and use its methods
myS = CStack()
flg = True# Used to check if more input needed
while flg:
myInp = input('For PUSH enter 1, For POP 2, For Display stack reversed 3 ')
myInt = int(myInp)
if myInt == 1:
myResp = input('Enter item to push ')
myS.push(myResp)
elif myInt == 2:
myS.myPop()
elif myInt == 3:
myS.stRev()
else:
print('Wrong Input')
checkContinue = input('Press y to continue, any other key to exit')
if checkContinue != 'y':
flg = False# Turning flg False will terminate the while loop
17.4.4. Queue
Note that list objects have two methods: append() and insert().
For list.insert(Idx, item): You can pick where the value will be added to the list. You can only add one value to a list at a time. Each value you insert to a list is considered one element.
For list.append(item): You cannot pick where the value will be added to the list (it will be added as the last value).
For a queue the first item added will be at index 0 and the next at index 1 and so on. So use the method append() and not insert() because you will be adding the items only at the end, i.e., rear of the list.
Script implementing queue in Python (without using classes)
This script is available on page 437 of the book
myQ = []
flg = True
while flg:
print("1 for insert, 2 for delete, 3 for display->")
choice = input("Enter choice->")
if not choice.isnumeric(): # If user doesnt type number again ask for input
print("You must type a number")
continue
elif int(choice) ==1: # In 3.x must cast choice to int
item = input("Enter new number")
myQ.append(item)
elif int(choice) == 2:
if myQ ==[]: # Check if queue is empty
print("Cannot delete as queue is empty")
else:
print("Deleted item is", myQ[0])
del myQ[0]
elif int(choice) ==3:
for i in range(0, len(myQ)):
print(myQ[i])
else:
print("Wrong input")
myInput = input("Press y to continue, any other key to exit")
if myInput != 'y':
flg = False
The following code shows the implementation of a queue using a Que class:
This script is available on page 438 of the book
class Que:
def __init__(self):
self.myQ = []
def enQueue(self, item):
self.myQ.append(item)
def deQueue(self):
if self.myQ ==[]:
print("Que empty so cant deque")
else:
deleted = self.myQ.pop(0)
return deleted
def prQueue(self):
if self.myQ ==[]:
print("Que empty so cant print")
else:
x = len(self.myQ)
for i in range(0, x):
print('Item at index ', i, 'is->',q.myQ[i])
q = Que() # Create an object of Que class
flg = True
while flg == True: # Cannot exit till flg becomes False
print("1 for input 2 for delete 3 for display. Any other key to exit")
choice = input("Enter your choice")
if not choice.isnumeric(): # Make sure that if non numeric input then exit
print("Exiting...")
break
elif(int(choice)== 1):
b = input("Enter new item")
q.enQueue(b)
elif(int(choice) == 2):
itm = q.deQueue()
print("Deleted item->", itm)
elif(int(choice) == 3):
q.prQueue()
else:
print("Exiting.......")
flg = False
17.4.6. Implementing a queue using front and rear variables
Earlier in the chapter, there was a discussion on queue using two variables say front (or head) and rear (or tail). You may implement a queue algorithm using front and rear as follows:
enQueue) to the queue, you will increment the rear by 1 and if you delete an item (deQueue), you will increment the front head by one. front == rear, then Que is empty. So if front == rear, you should not deque.The following script shows the implementation
This script is available on page 440 of the book
class Que:
def __init__(self):
self.myQ = []
self.front = self.rear = -1# front, rear hold index of head and tail
def enQueue(self, item):
self.myQ.append(item)
self.rear =self.rear + 1# On enque increment rear
def deQueue(self):
if self.front >= self.rear: # front should always be less than rear
print("Que empty so cant deque")
else:
deleted = self.myQ.pop(0)
self.front = self.front + 1# on deque increment front
return deleted
def prQueue(self):
if self.front == self.rear:
print("Que empty so cant print")
else:
x = len(self.myQ)
for i in range(0, x):
print('Item at index ', i, 'is->',q.myQ[i])
q = Que() # Create an object of Que class
flg = True
while flg == True: # Cannot exit till flg becomes False
print("1 for input 2 for delete 3 for display. Any other key to exit")
choice = input("Enter your choice")
if not choice.isnumeric(): # Make sure that if non numeric input then exit
print("Exiting...")
break
elif(int(choice)== 1):
b = input("Enter new item")
q.enQueue(b)
elif(int(choice) == 2):
itm = q.deQueue()
print("Deleted item->", itm)
elif(int(choice) == 3):
q.prQueue()
else:
print("Exiting.......")
flg = False